package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class FindElementsInAContaminatedBinaryTree {
	public static class FindElements {

		private TreeNode root;
		
	    public FindElements(TreeNode root) {
	        this.root = root;
	    }
	    
	    public boolean find(int target) {
	    	TreeNode p = root;
	    	target++;
	    	
	    	int temp = 0;
	    	//指向target最左二数位
	    	for(int i = 1; (target >> i) > 0; i++)
	    		temp = temp == 0 ? 1 : temp << 1;
	    	
	    	while(temp > 0) {
	    		boolean left = (target & temp) == 0;
	    		
	    		if(p.left == null && left || p.right == null && !left)
	    			return false;
	    		
	    		p = left ? p.left : p.right;
	    		temp >>>= 1;
	    	}
	        return true;
	    }	    
	}
}
